package com.xgy.ordering.collection;
/*
 * SmartList - 针对小尺寸优化的基于数组的列表
 * 继承AbstractList以获得更好的代码复用和性能优化
 *
 * 设计目标：
 *  - 对小列表（0-1个元素）的最佳性能：避免分配Object[]
 *  - 对中等/大列表的竞争性性能：使用System.arraycopy实现快速get、add、remove操作
 *  - 低GC压力：仅在size >= 2时分配后备数组
 *  - 快速失败迭代器
 *
 * 行为：
 *  - 在单个Object"data"字段中内部存储元素。
 *    - data == null: size == 0
 *    - data instanceof Object: size == 1，data是元素本身
 *    - data instanceof Object[]: size >= 2，data是后备数组
 *  - 维护显式的int size字段和modCount用于迭代器快速失败语义。
 *

 * 性能优化：
 *  - 继承AbstractList，复用其优化的迭代器和批量操作
 *  - 对小尺寸列表（0-1元素）零数组分配
 *  - 对中等尺寸使用System.arraycopy进行高效操作
 *  - 支持RandomAccess接口，提供O(1)随机访问
 *
 * 注意事项/权衡：
 *  - 此实现专注于单线程性能（无同步）。
 *  - 支持null元素。
 *  - 对于大规模/高并发场景，请考虑分段结构或原始类型特化。
 */

import java.io.Serializable;
import java.util.*;

public class SmartList<E> extends AbstractList<E> implements RandomAccess, Cloneable, Serializable {
    private static final long serialVersionUID = 1L;

    // 当data == null => size == 0
    // 当data是Object（非数组）=> size == 1
    // 当data是Object[] => size >= 2，数组可能比'size'大
    private transient Object data;
    private transient int size;
    private transient int modCount;

    private static final int DEFAULT_CAPACITY = 8; // 较小但避免转换后频繁调整大小

    public SmartList() {
        this.data = null;
        this.size = 0;
    }

    public SmartList(Collection<? extends E> c) {
        Objects.requireNonNull(c);
        int csize = c.size();
        if (csize == 0) {
            data = null;
            size = 0;
        } else if (csize == 1) {
            data = c.iterator().next();
            size = 1;
        } else {
            Object[] arr = new Object[csize];
            int i = 0;
            for (E e : c) arr[i++] = e;
            data = arr;
            size = csize;
        }
    }

    // 辅助方法：检查索引是否在[0,size)范围内
    private void rangeCheck(int index) {
        if (index < 0 || index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private void rangeCheckForAdd(int index) {
        if (index < 0 || index > size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private String outOfBoundsMsg(int index) {
        return "Index: " + index + ", Size: " + size;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean contains(Object o) {
        return indexOf(o) != -1;
    }

    @Override
    public Object[] toArray() {
        if (size == 0) return new Object[0];
        if (size == 1) return new Object[]{data};
        Object[] arr = (Object[]) data;
        return Arrays.copyOf(arr, size);
    }

    @SuppressWarnings("unchecked")
    @Override
    public <T> T[] toArray(T[] a) {
        if (a.length < size) {
            // 创建新的T类型数组
            return (T[]) Arrays.copyOf(toArray(), size, a.getClass());
        }
        if (size == 0) {
            if (a.length > 0) a[0] = null;
            return a;
        }
        if (size == 1) {
            a[0] = (T) data;
            if (a.length > 1) a[1] = null;
            return a;
        }
        System.arraycopy(data, 0, a, 0, size);
        if (a.length > size) a[size] = null;
        return a;
    }

    @SuppressWarnings("unchecked")
    @Override
    public E get(int index) {
        rangeCheck(index);
        if (size == 1) return (E) data;
        Object[] arr = (Object[]) data;
        return (E) arr[index];
    }

    @SuppressWarnings("unchecked")
    @Override
    public E set(int index, E element) {
        rangeCheck(index);
        if (size == 1) {
            E old = (E) data;
            data = element;
            modCount++;
            return old;
        }
        Object[] arr = (Object[]) data;
        E old = (E) arr[index];
        arr[index] = element;
        modCount++;
        return old;
    }

    @Override
    public boolean add(E e) {
        if (size == 0) {
            data = e;
            size = 1;
        } else if (size == 1) {
            Object[] arr = new Object[DEFAULT_CAPACITY];
            arr[0] = data;
            arr[1] = e;
            data = arr;
            size = 2;
        } else {
            Object[] arr = (Object[]) data;
            if (size == arr.length) {
                int newCap = newCapacity(arr.length);
                arr = Arrays.copyOf(arr, newCap);
                data = arr;
            }
            arr[size] = e;
            size++;
        }
        modCount++;
        return true;
    }

    @Override
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        if (size == 0) {
            if (index != 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
            data = element;
            size = 1;
        } else if (size == 1) {
            // 转换为数组
            Object[] arr = new Object[DEFAULT_CAPACITY];
            if (index == 0) {
                arr[0] = element;
                arr[1] = data;
            } else {
                arr[0] = data;
                arr[1] = element;
            }
            data = arr;
            size = 2;
        } else {
            Object[] arr = (Object[]) data;
            if (size == arr.length) {
                int newCap = newCapacity(arr.length);
                Object[] newArr = new Object[newCap];
                System.arraycopy(arr, 0, newArr, 0, index);
                newArr[index] = element;
                System.arraycopy(arr, index, newArr, index + 1, size - index);
                data = newArr;
            } else {
                System.arraycopy(arr, index, arr, index + 1, size - index);
                arr[index] = element;
            }
            size++;
        }
        modCount++;
    }

    @SuppressWarnings("unchecked")
    @Override
    public E remove(int index) {
        rangeCheck(index);
        if (size == 1) {
            E old = (E) data;
            data = null;
            size = 0;
            modCount++;
            return old;
        }
        Object[] arr = (Object[]) data;
        E old = (E) arr[index];
        int numMoved = size - index - 1;
        if (numMoved > 0) System.arraycopy(arr, index + 1, arr, index, numMoved);
        arr[--size] = null; // 帮助GC
        if (size == 1) {
            // 折叠为单元素表示
            Object single = arr[0];
            data = single;
        }
        modCount++;
        return old;
    }

    @Override
    public boolean remove(Object o) {
        int idx = indexOf(o);
        if (idx == -1) return false;
        remove(idx);
        return true;
    }

    @Override
    public void clear() {
        if (size == 0) return;
        if (size >= 2) {
            Object[] arr = (Object[]) data;
            Arrays.fill(arr, 0, size, null);
        }
        data = null;
        size = 0;
        modCount++;
    }

    @Override
    public int indexOf(Object o) {
        if (size == 0) return -1;
        if (size == 1) return Objects.equals(data, o) ? 0 : -1;
        Object[] arr = (Object[]) data;
        if (o == null) {
            for (int i = 0; i < size; i++) if (arr[i] == null) return i;
        } else {
            for (int i = 0; i < size; i++) if (o.equals(arr[i])) return i;
        }
        return -1;
    }

    @Override
    public int lastIndexOf(Object o) {
        if (size == 0) return -1;
        if (size == 1) return Objects.equals(data, o) ? 0 : -1;
        Object[] arr = (Object[]) data;
        if (o == null) {
            for (int i = size - 1; i >= 0; i--) if (arr[i] == null) return i;
        } else {
            for (int i = size - 1; i >= 0; i--) if (o.equals(arr[i])) return i;
        }
        return -1;
    }

    @Override
    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }

    @Override
    public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index);
        Objects.requireNonNull(c);
        int csize = c.size();
        if (csize == 0) return false;
        if (size == 0 && csize == 1) {
            // 一次性优化 -> 变为单元素
            E e = c.iterator().next();
            data = e;
            size = 1;
            modCount++;
            return true;
        }
        if (size == 1) {
            // 转换为数组
            Object[] arr = new Object[Math.max(DEFAULT_CAPACITY, size + csize)];
            if (index == 0) {
                int i = 0;
                for (E e : c) arr[i++] = e;
                arr[i++] = data;
            } else {
                arr[0] = data;
                int i = 1;
                for (E e : c) arr[i++] = e;
            }
            data = arr;
            size += csize;
            modCount++;
            return true;
        }
        // size >= 2
        // 安全检查：确保data确实是数组
        if (!(data instanceof Object[])) {
            // 如果data不是数组，说明状态不一致，重新处理
            if (size == 0) {
                // 空列表，直接添加所有元素
                if (csize == 1) {
                    // 单个元素，使用单元素模式
                    E e = c.iterator().next();
                    data = e;
                    size = 1;
                } else {
                    // 多个元素，使用数组模式
                    Object[] arr = new Object[Math.max(DEFAULT_CAPACITY, csize)];
                    int i = 0;
                    for (E e : c) arr[i++] = e;
                    data = arr;
                    size = csize;
                }
                modCount++;
                return true;
            } else if (size == 1) {
                // 转换为数组
                Object[] arr = new Object[Math.max(DEFAULT_CAPACITY, size + csize)];
                if (index == 0) {
                    int i = 0;
                    for (E e : c) arr[i++] = e;
                    arr[i++] = data;
                } else {
                    arr[0] = data;
                    int i = 1;
                    for (E e : c) arr[i++] = e;
                }
                data = arr;
                size += csize;
                modCount++;
                return true;
            } else {
                // 这是不应该发生的情况，抛出异常
                throw new IllegalStateException("Invalid internal state: size=" + size + ", data type=" + (data == null ? "null" : data.getClass().getName()));
            }
        }
        
        Object[] arr = (Object[]) data;
        int need = size + csize;
        if (need > arr.length) {
            int newCap = Math.max(newCapacity(arr.length), need);
            Object[] newArr = new Object[newCap];
            System.arraycopy(arr, 0, newArr, 0, index);
            int i = index;
            for (E e : c) newArr[i++] = e;
            System.arraycopy(arr, index, newArr, i, size - index);
            data = newArr;
        } else {
            // 先移动现有元素，为插入腾出空间
            System.arraycopy(arr, index, arr, index + csize, size - index);
            // 插入新元素
            int i = index;
            for (E e : c) arr[i++] = e;
        }
        size += csize;
        modCount++;
        return true;
    }

    @SuppressWarnings("unchecked")
    @Override
    public SmartList<E> clone() {
        try {
            SmartList<E> v = (SmartList<E>) super.clone();
            if (size >= 2) {
                Object[] arr = (Object[]) data;
                v.data = Arrays.copyOf(arr, arr.length);
            }
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            throw new InternalError(e);
        }
    }

    // --- 辅助方法 ---
    private int newCapacity(int old) {
        // 按1.5倍增长，但至少+1
        int newCap = old + (old >> 1);
        if (newCap <= old) newCap = old + 1;
        return newCap;
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        for (Object e : c) if (!contains(e)) return false;
        return true;
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
        boolean modified = false;
        for (Iterator<E> it = iterator(); it.hasNext(); ) {
            if (c.contains(it.next())) {
                it.remove();
                modified = true;
            }
        }
        return modified;
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        Objects.requireNonNull(c);
        boolean modified = false;
        for (Iterator<E> it = iterator(); it.hasNext(); ) {
            if (!c.contains(it.next())) {
                it.remove();
                modified = true;
            }
        }
        return modified;
    }

    @Override
    public Iterator<E> iterator() {
        return listIterator(0);
    }

    @Override
    public ListIterator<E> listIterator() {
        return listIterator(0);
    }

    @Override
    public ListIterator<E> listIterator(int index) {
        rangeCheckForAdd(index);
        return new ListItr(index);
    }

    private class ListItr implements ListIterator<E> {
        private int cursor;
        private int lastRet = -1;
        private int expectedModCount = modCount;

        ListItr(int index) {
            cursor = index;
        }

        @Override
        public boolean hasNext() {
            return cursor != size;
        }

        @SuppressWarnings("unchecked")
        @Override
        public E next() {
            checkForComodification();
            if (cursor >= size) throw new NoSuchElementException();
            E result;
            if (size == 1) {
                result = (E) data;
            } else {
                Object[] arr = (Object[]) data;
                result = (E) arr[cursor];
            }
            lastRet = cursor++;
            return result;
        }

        @Override
        public boolean hasPrevious() {
            return cursor != 0;
        }

        @SuppressWarnings("unchecked")
        @Override
        public E previous() {
            checkForComodification();
            if (cursor <= 0) throw new NoSuchElementException();
            cursor--;
            E result;
            if (size == 1) {
                result = (E) data;
            } else {
                Object[] arr = (Object[]) data;
                result = (E) arr[cursor];
            }
            lastRet = cursor;
            return result;
        }

        @Override
        public int nextIndex() {
            return cursor;
        }

        @Override
        public int previousIndex() {
            return cursor - 1;
        }

        @Override
        public void remove() {
            if (lastRet < 0) throw new IllegalStateException();
            checkForComodification();
            try {
                SmartList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException e) {
                throw new ConcurrentModificationException();
            }
        }

        @Override
        public void set(E e) {
            if (lastRet < 0) throw new IllegalStateException();
            checkForComodification();
            try {
                SmartList.this.set(lastRet, e);
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        @Override
        public void add(E e) {
            checkForComodification();
            try {
                int i = cursor;
                SmartList.this.add(i, e);
                cursor = i + 1;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        final void checkForComodification() {
            if (modCount != expectedModCount) throw new ConcurrentModificationException();
        }
    }

    @Override
    public List<E> subList(int fromIndex, int toIndex) {
        throw new UnsupportedOperationException("SmartList中未实现subList；请使用new ArrayList<>(smartList).subList(...)");
    }

    @Override
    public int hashCode() {
        int h = 1;
        for (int i = 0; i < size; i++) {
            Object o = (size == 1) ? data : ((Object[]) data)[i];
            h = 31 * h + (o == null ? 0 : o.hashCode());
        }
        return h;
    }

    @Override
    public boolean equals(Object o) {
        if (o == this) return true;
        if (!(o instanceof List)) return false;
        List<?> other = (List<?>) o;
        if (other.size() != size) return false;
        Iterator<?> it = other.iterator();
        for (int i = 0; i < size; i++) {
            Object a = (size == 1) ? data : ((Object[]) data)[i];
            Object b = it.next();
            if (!Objects.equals(a, b)) return false;
        }
        return true;
    }

    // 继承AbstractList的迭代器实现，无需自定义迭代器
    // AbstractList已经提供了优化的迭代器实现

    // --- 批量操作辅助方法 ---
    @Override
    public String toString() {
        if (size == 0) return "[]";
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        for (int i = 0; i < size; i++) {
            Object e = (size == 1) ? data : ((Object[]) data)[i];
            sb.append(e == this ? "(this Collection)" : String.valueOf(e));
            if (i != size - 1) sb.append(',').append(' ');
        }
        sb.append(']');
        return sb.toString();
    }

    // ========== 性能监控和诊断方法 ==========

    /**
     * 获取存储模式信息
     */
    public String getStorageInfo() {
        if (size == 0) {
            return "EmptyMode[size=0]";
        } else if (size == 1) {
            return "SingleElementMode[size=1]";
        } else {
            Object[] arr = (Object[]) data;
            return String.format("ArrayMode[capacity=%d, size=%d, usage=%.1f%%]",
                    arr.length, size, (size * 100.0 / arr.length));
        }
    }

    /**
     * 获取当前存储模式
     */
    public String getCurrentMode() {
        if (size == 0) {
            return "EMPTY";
        } else if (size == 1) {
            return "SINGLE_ELEMENT";
        } else {
            return "ARRAY";
        }
    }

    /**
     * 手动触发优化（用于测试和诊断）
     */
    public void optimize() {
        // 对于当前实现，优化主要是确保数组容量合理
        if (size >= 2) {
            Object[] arr = (Object[]) data;
            if (arr.length > size * 2) {
                // 如果数组容量远大于实际大小，进行压缩
                data = Arrays.copyOf(arr, Math.max(size, DEFAULT_CAPACITY));
                modCount++;
            }
        }
    }
}